package graph;

import org.junit.Test;

import java.util.*;

public class CourseSchedule210 {

    @Test
    public void test() {
        PostorderTraverse p = new PostorderTraverse();
        p.findOrder(2, new int[][]{new int[]{0, 1}, new int[]{1, 0}});
        p.findOrder(2, new int[][]{new int[]{1, 0}});
        p.findOrder(4, new int[][]{new int[]{1, 0}, new int[]{2, 0}, new int[]{3, 1}, new int[]{3, 2}});

        BFSTraverse b = new BFSTraverse();
        b.findOrder(2, new int[][]{new int[]{0, 1}, new int[]{1, 0}});
        b.findOrder(2, new int[][]{new int[]{1, 0}});
        b.findOrder(4, new int[][]{new int[]{1, 0}, new int[]{2, 0}, new int[]{3, 1}, new int[]{3, 2}});
    }

    static class BFSTraverse {
        public int[] findOrder(int n, int[][] pr) {
            // 出度
            List<List<Integer>> g = buildGraphOutEdge(n, pr);

            Queue<Integer> q = new LinkedList<>();
            // 入度
            int[] inedges = new int[n];
            Arrays.fill(inedges, 0);

            for (int i = 0; i < n; i++) {
                // 入度赋值
                for (int next: g.get(i)) {
                    inedges[next]++;
                }
            }

            // 初始时, 放入
            for (int i = 0; i < n; i++) {
                if (inedges[i] == 0) {
                    q.offer(i);
                }
            }

            // 最终排序结果
            int[] orders = new int[n];
            int count = 0;
            Integer curr;
            while ((curr = q.poll()) != null) {
                orders[count] = curr;
                count++;
                for (Integer next: g.get(curr)) {
                    inedges[next]--;
                    if (inedges[next] == 0) {
                        // 发现新节点
                        q.offer(next);
                    }
                }
            }
            int[] result = (count == n) ? orders : new int[0];
            System.out.format("n: %d, g: %s, orders: %s\n", n, g, Arrays.toString(result));
            return result;
        }

        public static List<List<Integer>> buildGraphOutEdge(int n, int[][] pr) {
            List<List<Integer>> g = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                g.add(new ArrayList<>(n));
            }
            // 注意本题依赖定义是反的, 比如[0,1]表示0依赖1
            for (int[] edge : pr) {
                // 出度
                g.get(edge[1]).add(edge[0]);
            }
            return g;
        }
    }

    // 建表的时候, 注意本题依赖定义是反的, 比如[0,1]表示0依赖1
    static class PostorderTraverse {
        public int[] findOrder(int n, int[][] pr) {
            List<List<Integer>> g = buildGraph(n, pr);

            // 在之前的所有遍历中, 被访问过了
            boolean[] visited = new boolean[n];

            // 当前这轮遍历的路径, 需要回溯
            boolean[] path = new boolean[n];

            // 记录后序遍历的
            List<Integer> postorders = new ArrayList<>(n);

            Arrays.fill(visited, false);

            // 可能有多个起点, 每个都访问一遍, 不然就遍历少了
            for (int i = 0; i < n; i++) {
                // 避免重复访问
                if (!visited[i]) {
                    if (!traverseAndCheckCircle(i, path, postorders, visited, g)) {
                        System.out.format("circle from i: %d\n", i);
                        return new int[0];
                    }
                }
            }
            int[] orders = new int[n];
            for (int i = 0; i < n; i++) {
                orders[i] = postorders.get(n-i-1);
            }
            System.out.format("n: %d, g: %s, orders: %s\n", n, g, Arrays.toString(orders));
            return orders;
        }

        // 递归遍历所有节点, 记录是否被访问
        public boolean traverseAndCheckCircle(int index, boolean[] path, List<Integer> postorders, boolean[] visited, List<List<Integer>> g) {
            if (path[index]) {
                // 发现环了
                return false;
            }
            if (visited[index]) {
                // 已经被访问过了, 不能重复访问. 所以直接返回"无环".
                return true;
            }
            visited[index] = true;
            path[index] = true;
            for (Integer next : g.get(index)) {
                if (!traverseAndCheckCircle(next, path, postorders, visited, g)) {
                    return false;
                }
            }
            path[index] = false;
            // 这里比较精巧, 加入后序队列. 越是先被递归的, 越是靠后放入.
            postorders.add(index);
            return true;
        }

        // 先建立邻接表
        public static List<List<Integer>> buildGraph(int n, int[][] pr) {
            List<List<Integer>> g = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                g.add(new ArrayList<>(n));
            }
            // 注意本题依赖定义是反的, 比如[0,1]表示0依赖1
            for (int[] edge : pr) {
                //g.get(edge[0]).add(edge[1]);
                g.get(edge[1]).add(edge[0]);
            }
            return g;
        }
    }
}
